// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore()
{
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
Semaphore::P()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V()
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

#ifdef CHANGED
/**
Creates a new Lock.  Locks are similar to semaphores, but only have a single locked value
*/
Lock::Lock(char* debugName) 
{
	name = debugName;
	//current locked value
	isLocked = false;
	//pointer to thread that owns this
	ownerThread = NULL;
	//queue of waiting threads
	queue = new List;
}

/**
Destructs a Lock, releasing all of the Lock's waiting threads.
*/
Lock::~Lock() 
{
	//release all waiting threads
	while(!queue->IsEmpty())
	{
		scheduler->ReadyToRun((Thread*)queue->Remove());
	}
	//delete waiting queue
	delete queue;
}

bool Lock::isQueueEmpty()
{
	return queue->IsEmpty();
}

/**
Acquires the Lock, blocking if the Lock is unavailable
*/
void Lock::Acquire() 
{
	//disable interrupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	
	//printf("%s: Acquire() method of %s called\n", currentThread->getName(), name);
	
	//if current thread is lock owner, restore interrupts and return
	if(currentThread == ownerThread)
	{
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	//if lock is unlocked, lock it and make current thread owner
	if(!isLocked)
	{
		//printf("%s: Acquiring Lock %s\n", currentThread->getName(), name);
		isLocked = true;
		ownerThread = currentThread;
	}
	//if lock is locked, add current thread to lock's waiting queue and tell current thread to sleep
	else
	{
		queue->Append((void*)currentThread);
		
		//printf("%s appended to waiting queue of %s\n", currentThread->getName(), name);
		
		currentThread->Sleep();
		
		//printf("%s woke from lock %s\n", currentThread->getName(), name);
	}
	
	//restore interrupts and return
	(void) interrupt->SetLevel(oldLevel);
}

/**
Releases a Lock.  Successful only if the current thread owns the Lock.
*/
void Lock::Release() 
{
	//disable interrupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	//if current thread is not owner of lock, print error and restore interrupts and return
	if(ownerThread != currentThread)
	{
		DEBUG('t', "Thread is not owner of Lock!", name);
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	//printf("Lock %s has been released by %s\n", name, currentThread->getName());
	
	//else if wait queue does not contain any threads, unlock lock and set the lock's owner to null
	if(queue->IsEmpty())
	{
		isLocked = false;
		ownerThread = NULL;
	
		(void) interrupt->SetLevel(oldLevel);
	}
	else
	{
		//else if wait queue contains a thread, wake the thread up and update the lock's owner
		Thread* nextThread = (Thread*) queue->Remove();
		ownerThread = nextThread;
		scheduler->ReadyToRun(nextThread);
		
		//printf("%s has been released to the scheduler by %s\n", nextThread->getName(), currentThread->getName());
		
		//restore interrupts and return
		(void) interrupt->SetLevel(oldLevel);
	}
}

/**
Returns whether the Lock's owner is the current thread
*/
bool Lock::isHeldByCurrentThread()
{
	return (currentThread == ownerThread);
}

Condition::Condition(char* debugName)
{
	name = debugName;

	//Initialize the waiting queue
	m_queue = new List;
	
	//initialize m_waitingLock to be NULL
	m_waitingLock = NULL;
}

Condition::~Condition() 
{
	//Just destroy the waiting queue and put all the threads in it on the ready queue in scheduler
	while(!m_queue->IsEmpty())
	{
		scheduler->ReadyToRun((Thread*)m_queue->Remove());
	}
	
	delete m_queue;
}

bool Condition::isQueueEmpty()
{
	return m_queue->IsEmpty();
}

void Condition::Wait(Lock* conditionLock)
{
	//Disable interrupt for current thread
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	
	//if conditionLock is NULL someone is trying to be funny, restore interrupt for current thread and exit
	if(conditionLock == NULL)
	{
		DEBUG('t', "conditionLock cannot be NULL!", name);
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	//if conditions's m_waitingLock is null it means its the first time a thread is waiting on this condition so just assign conditionLock to m_waitingLock
	if(m_waitingLock == NULL)
	{
		m_waitingLock = conditionLock;
	}
	
	//check if m_waitingLock is the same as conditionLock if not again some one is trying to break mutually exclusive access - ERROR
	//if they are not equal print error, restore interrupts for current thread and return
	if(m_waitingLock != conditionLock)
	{
		DEBUG('t', "conditionLock was different than the monitor's Lock!", name);
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	//Now its ok to wait
	
	//before going to sleep release the lock so others can enter the monitor
	m_waitingLock->Release();
	
	//add current thread to to wait queue for the condition
	m_queue->Append((void*)currentThread);
	
	//put current thread to sleep
	currentThread->Sleep();
	
	//the current thread waits at this code point until it is signalled:
	//printf("%s has woken up\n", currentThread->getName());
	
	//printf("conditionLock: %i\n", conditionLock);
	//printf("m_waitingLock: %i\n", m_waitingLock);
	
	//we should acquire the lock again for mutual exclusivity
	//Be carefull: dont use m_waitingLock->Acquire() as it might have already been set to null if this thread is the last thread being signaled
	conditionLock->Acquire();
	
	//printf("%s acquired Lock %s successfully\n", currentThread->getName(), conditionLock->getName());
	
	//BE CAREFULL: when we are making the decision to enter in a wait state in our monitor we should keep that check in while loop like this:
	//while(are condition is not met)
	//	condition.wait(lock);
	//becauase when the waiting thread is signalled and let loose before it take time slice in cpu the condition might change by other threads
	//so we should keep chacking and making sure condition is satisfied even after waking up from a wai
	
	//Restore Interrupt for current thread
	(void) interrupt->SetLevel(oldLevel);
}

void Condition::Signal(Lock* conditionLock)
{
	//disable interrupts for current thread
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	
	//if coditionLock is NULL someone is trying to be funny, restore interrupt for current thread and exit
	if(conditionLock == NULL)
	{
		DEBUG('t', "conditionLock cannot be NULL!", name);
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	//check if m_waitingLock is the same as conditionLock if not again some one is trying to break mutually exclusive access - ERROR
	//if they are not equal print error, restore interrupts for current thread and return
	if(m_waitingLock != conditionLock)
	{
		DEBUG('t', "conditionLock was different than the monitor's Lock!", name);
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	//if there are no waiters in condition variable's queue then restore interrupts and return - Nothing to do
	if(m_queue->IsEmpty())
	{
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	//since there are threads in the queue, wake the next thread by moving it from the waiting queue to the scheduler
	Thread* nextThread = (Thread*) m_queue->Remove();
	scheduler->ReadyToRun(nextThread);
	
	//if we ran out of waiters then set the objects lock to null we don't need it anymore
	if(m_queue->IsEmpty())
	{
		m_waitingLock = NULL;
	}
	
	//restore interrupt for current thread and return
	(void) interrupt->SetLevel(oldLevel);
}

void Condition::Broadcast(Lock* conditionLock)
{
/*
	//if conditionLock is NULL someone is trying to be funny, restore interrupt for current thread and exit
	if(conditionLock == NULL)
	{
		DEBUG('t', "conditionLock cannot be NULL!", name);
		return;
	}
	
	//check if m_waitingLock is the same as conditionLock if not again some one is trying to break mutually exclusive access - ERROR
	//if they are not equal print error, restore interrupts for current thread and return
	if(m_waitingLock != conditionLock)
	{
		DEBUG('t', "conditionLock was different than the monitor's Lock!", name);
		return;
	}
*/
	//while we have threads in our waiting queue call signal on them
	while(!m_queue->IsEmpty())
	{
		Signal(conditionLock);
	}
	
	//we dont need to disable interrupt in this method because
	//everytime we want to signal a thread we make sure they exist
	//in the waiting queue so we dont need the whole while loop to
	//be atomic operation
}
#endif //CHANGED
